package weekMatch.one_345;

import java.util.*;

public class LeeCode_03_02 {
    public static void main(String[] args) {
//        System.out.println(countCompleteComponents(6, new int[][]{{0, 1}, {0, 2}, {1, 2}, {3, 4}, {3, 5}}));
        System.out.println(countCompleteComponents(4, new int[][]{{1,0}, {0, 2}, {3, 2}, {3, 1}}));
    }
    private static int countCompleteComponents(int n, int[][] edges) {
        int[] du = new int[n];
        int[][] grid = new int[n][n];
        for (int i = 0; i < n; i++) {
            grid[i][i] = 1;
        }
        for (int[] edge : edges) {
            grid[edge[0]][edge[1]] = 1;
            grid[edge[1]][edge[0]] = 1;
            du[edge[0]]++;
            du[edge[1]]++;
        }
        Set<Integer> used = new HashSet<>();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (used.contains(i))
                continue;
            Set<Integer> set = new HashSet<>();
            bfs(grid, set, i);
            boolean flag = true;
            for (Integer node : set) {
                used.add(node);
                if (du[node] != set.size() - 1){
                    flag = false;
                    break;
                }
            }
            if (flag){
                ans++;
            }
        }
        return ans;
    }
    private static void bfs(int[][] grid, Set<Integer> set, int node){
        if (set.contains(node)) {
            return;
        }
        set.add(node);
        for (int i = 0; i < grid[node].length; i++) {
            if (grid[node][i] == 1){
                bfs(grid, set, i);
            }
        }
    }
}
